def update_matrix(matrix):
    m = len(matrix)
    n = len(matrix[0])
    conqueror = []  # 存放殖民者坐标

    # 找到所有的初代殖民者0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                conqueror.append((i, j))

    # 开始殖民扩张
    while len(conqueror) > 0:
        x, y = conqueror.pop(0)
        for x_bias, y_bias in [[0, -1], [-1, 0], [0, 1], [1, 0]]:
            x_ = x + x_bias
            y_ = y + y_bias
            if 0 <= x_ < m and 0 <= y_ < n and matrix[x_][y_] > 0:
                matrix[x_][y_] = matrix[x][y] - 1
                conqueror.append((x_, y_))

    for i in range(m):
        for j in range(n):
            matrix[i][j] = -matrix[i][j]

    return matrix


if __name__ == '__main__':
    print(update_matrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]]))
